package com.le.enhance.class4;

import org.junit.Test;

/**
 * 给定一棵二叉树的头节点head，请返回最大搜索二叉子树的大小
 */
public class Code_04_BiggestSubBSTInTree {

    public static class Node {
        public int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static class ReturnType {
        public int size;
        Node head;
        public int min;
        public int max;

        public ReturnType(int size, Node head, int min, int max) {
            this.size = size;
            this.head = head;
            this.min = min;
            this.max = max;
        }
    }

    public static ReturnType process(Node head) {
        if (head == null) {
            return new ReturnType(0,null,Integer.MAX_VALUE,Integer.MIN_VALUE);
        }
        ReturnType leftSubTreeInfo = process(head.left);
        ReturnType rightSubTreeInfo = process(head.right);
        int includeItSelf = 0;
        if (leftSubTreeInfo.head == head.left
                && rightSubTreeInfo.head == head.right
                && leftSubTreeInfo.max < head.value
                && rightSubTreeInfo.min > head.value) {
            includeItSelf = leftSubTreeInfo.size + rightSubTreeInfo.size + 1;
        }
        int p1 = leftSubTreeInfo.size;
        int p2 = rightSubTreeInfo.size;
        int maxSize = Math.max(Math.max(p1, p2), includeItSelf);
        Node maxHead = p1 > p2 ? leftSubTreeInfo.head : rightSubTreeInfo.head;
        if (maxSize == includeItSelf){
            maxHead = head;
        }
        return new ReturnType(maxSize,
                maxHead,
                Math.min(Math.min(leftSubTreeInfo.min,rightSubTreeInfo.min),head.value),
                Math.max(Math.max(leftSubTreeInfo.max,rightSubTreeInfo.max),head.value)
        );
    }

    public static int getMaxLength(Node head){
        return process(head).size;
    }

    @Test
    public void test(){
        Node head = new Node(6);
        head.left = new Node(1);
        head.left.left = new Node(0);
        head.left.right = new Node(3);
        head.right = new Node(12);
        head.right.left = new Node(10);
        head.right.left.left = new Node(4);
        head.right.left.left.left = new Node(2);
        head.right.left.left.right = new Node(5);
        head.right.left.right = new Node(14);
        head.right.left.right.left = new Node(11);
        head.right.left.right.right = new Node(15);
        head.right.right = new Node(13);
        head.right.right.left = new Node(20);
        head.right.right.right = new Node(16);

        System.out.println(getMaxLength(head));
    }
}
